package MelbourneMap;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

/**
 * Graph object used to represent a graph data structure.
 * The graph is made up of {@link Node} and {@link Edge}
 * objects.
 * <p>
 * The main purpose of the graph is to represent a series 
 * of connections between nodes so that they can be searched
 * by path planning algorithms.
 * 
 * @author David Zappia, 7183216
 * @author Heong Jin Yu, 7019777
 *
 */
public class Graph 
{
	private Map<Integer, Node> nodeList = new HashMap<Integer, Node>();
	private Map<Integer, Map<Integer, Edge>> edgeList = new HashMap<Integer, Map<Integer, Edge>>();
	private int nextNodeID = 0;
	
	/**
	 * Constructor for the graph.
	 */
	public Graph()
	{
	}
	
	/**
	 * Checks if the graph is empty by checking its size.
	 * Returns true if empty and false otherwise.
	 * 
	 * @return		true if empty, false otherwise
	 */
	public boolean isEmpty()
	{
		if (nodeList.size() == 0)
			return true;
		else
			return false;
	}
	
	/**
	 * Checks the graph to see if the specified node
	 * index exists within the graph.
	 * 
	 * @param index		the unique node index to be checked
	 * @return			true if in graph, false otherwise
	 * @see 			Node
	 */
	public boolean isNode(int index)
	{
		if (nodeList.containsKey(index))
			return true;
		else
			return false;
	}
	
	/**
	 * Checks the graph to see if an edge exists between
	 * two nodes.
	 * 
	 * @param from		the index of the from node for the edge
	 * @param to		the index of the to node for the edge
	 * @return			true if the edge is in the graph, false otherwise
	 * @see				Edge
	 */
	public boolean isEdge(int from, int to)
	{
		if (edgeList.containsKey(from))
		{
			Map<Integer, Edge> edgesFrom = edgeList.get(from);
			
			if (edgesFrom.containsKey(to))
				return true;
		}
		
		return false;
	}
	
	/**
	 * Gets the {@link Node} object containing the
	 * unique id specified by index.
	 * 
	 * @param index		the unique ID of the node
	 * @return			the node referenced by the ID
	 */
	public Node getNode(int index)
	{
		return nodeList.get(index);
	}
	
	/**
	 * Gets the {@link Edge} object that joins the
	 * two nodes referenced by the from index and
	 * the to index.
	 * 
	 * @param from		the unique index of the from node in the requested edge
	 * @param to		the unique index of the to node in the requested
	 * @return			the edge object relating to the from and to nodes
	 * @see				Edge
	 */
	public Edge getEdge(int from, int to)
	{
		if (edgeList.containsKey(from))
		{
			Map<Integer, Edge> edgesFrom = edgeList.get(from);
			
			if (edgesFrom.containsKey(to))
				return edgesFrom.get(to);
		}
		
		return null;
	}
	
	/**
	 * Gets all the neighbours of the node relating
	 * to the unique index specified. Neighbour nodes
	 * are nodes that have a direct connection from the
	 * specified node.
	 * 
	 * @param index		the unique ID of the node to get the neighbours of
	 * @return			Set containing the IDs of the spcified nodes neighbours
	 */
	public Set<Integer> getNeighbours(int index)
	{
		if (edgeList.containsKey(index))
			return edgeList.get(index).keySet();
		
		return null;
	}
	
	/**
	 * Add a node to the graph and prepare a list
	 * of edges for the node.
	 * 
	 * @param n			the Node object to be added
	 * @return			the added Node object
	 */
	public Node addNode(Node n)
	{
		if (n.getID() < 0)
			n.setID(nextNodeID);
		nextNodeID ++;
		
		nodeList.put(n.getID(), n);
		edgeList.put(n.getID(), new HashMap<Integer, Edge>());
		
		return n;
	}
	
	/**
	 * Adds an edge object to the graph. The graph
	 * is a digraph so an edge returning from the
	 * specified edge is also added.
	 * 
	 * @param e		the edge object to be added
	 */
	public void addEdge(Edge e)
	{
		if (nodeList.containsKey(e.getFrom().getID()) && nodeList.containsKey(e.getTo().getID()))
		{
			Map<Integer, Edge> edgesFrom = edgeList.get(e.getFrom().getID());
			edgesFrom.put(e.getTo().getID(), e);
			e.getFrom().addEdge(e);
			e.getTo().addEdge(e);
			
			Map<Integer, Edge> edgesTo = edgeList.get(e.getTo().getID());
			Edge opp = new Edge(e.getTo(), e.getFrom());
			edgesTo.put(e.getFrom().getID(), opp);
			opp.getFrom().addEdge(opp);
			opp.getTo().addEdge(opp);
		}
	}
	
	/**
	 * Calculate the heuristic cost between the two
	 * specified Node objects. Based on straight line
	 * distance.
	 * 
	 * @param from		the from node
	 * @param to		the to node
	 * @return			the heuristic cost between the two nodes
	 */
	public double cost_h(Node from, Node to)
	{
		double x = Math.abs(to.getX() - from.getX());
		double y = Math.abs(to.getY() - from.getY());
		return (x*x + y*y);
	}
	
	/**
	 * Gets the number of nodes in the graph.
	 * 
	 * @return		the total nmber of nodes in the graph
	 */
	public int numNodes()
	{
		return nodeList.size();
	}
	
	/**
	 * Gets the total number of edges in the graph.
	 * 
	 * @return		the number of edges in the graph
	 */
	public int numEdges()
	{
		int sum = 0;
		
		for (Entry<Integer, Map<Integer, Edge>> entry : edgeList.entrySet())
			sum += entry.getValue().size();
		
		return sum;
	}
	
	/**
	 * Completely clear the graph removing all
	 * nodes and edges.
	 */
	public void clear()
	{
		nodeList.clear();
		edgeList.clear();
		nextNodeID = 0;
	}
	
	/**
	 * Gets a list of every single {@link Node} object that is contained
	 * within this graph.
	 * 
	 * @return		an ArrayList containing all the Node objects in the graph
	 */
	public ArrayList<Node> getNodeList()
	{
		return new ArrayList<Node>(nodeList.values());
	}
	

}
